#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using ti = tuple < int, int, int >;

int read() {
    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

const int N = 5e5 + 10;

int n, Q, d[N];
vector < ti > al;

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
	n = in, Q = in; int lst = 0; ll x = 1;
	rep(i, 1, n) {
		d[i] = in;
		if(d[i] > x) {
			al.eb(x, lst, i - 1);
			x = (d[i] + x - 1) / x * x; lst = i;
		}
	}
	al.eb(x, lst, n);
	while(Q--) {
		ll ans = 0, T = in, xl = in, xr = in;
		for(auto v : al) {
			ll d, x, y; tie(d, x, y) = v;
			ll l = T / d * d - y;
			ll r = T / d * d - x;
			ans += max(0ll, min(xr, r) - max(xl, l) + 1);
		}
		printf("%lld\n", ans);
	} return 0;
}
